package com.example.datastructure.find;

/**
 * 分块查找
 */
public class Blocksearch {
    //分块查找
    //index代表索引数组，st2代表待查找数组，keytype代表要查找的元素，m代表每块大,返回值为数组下标，若为-1，则表示没有此值
    public static int blocksearch(int[] index, int[] st2, int key, int m) {
        int i = shunxusearch(index, key);    //shunxunsearch函数返回值为带查找元素在第几块
        System.out.println("在第" + i + "块");
        if (i >= 0) {
            int j = m * i;   //j为第i块的第一个元素下标
            int curlen = (i + 1) * m;
            for (; j < curlen; j++) {       //遍历第i块值进行比较
                if (st2[j] == key)
                    return j;
            }
        }
        return -1;

    }

    /**
     * 从第一块最大值开始比较（下标为0），找到所在第几块
     * @param index
     * @param keytype
     * @return
     */
    public static int shunxusearch(int[] index, int keytype) {
        int i = 0;
        for (; i < index.length; i++) {
            if (keytype <= index[i]) {
                break;
            }
            if(i==index.length-1){      //若i == index.length-1 则表示已经是最后一个块了，上一个判断不成功说明最后一个块也没有此值
                return -1;
            }
        }
        return i;
    }

    public static void main(String args[]) {
        int index[] = {22, 48, 86};
        int st2[] = {22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48, 60, 58, 74, 49, 86, 53};
        System.out.println("分块查找");
        System.out.println(blocksearch(index, st2, 2, 6));
    }
}
